package sudoku;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Stack;
import java.util.TreeMap;
import java.util.logging.Level;
import java.util.logging.Logger;

/**
 * This Class will try to solve classic sudoku board. 
 * Also provides time predictions left until end of solution process. 
 * @author Taras Basiuk
 * @version 0.1
 */
public class ClassicGridSolution implements Runnable{
   
    /** Instance of ClassicGrid copy.*/
    private ClassicGrid grid;
    
    /** 
     * Stack contains numbers of cells where algorithm made turns. 
     * Helps to differ original cells from ones with algorithm created values.
     */
    private Stack<Integer> turns;
    
    /** ArrayList with numbers of empty cells on the board. */
    private ArrayList<Integer> emptyCellsNum;
    
    /** ArrayList where all found solutions go.*/
    private ArrayList<TreeMap<Integer, ClassicCell>> solutionsFound;
    
    /** Maximum index for cell number on the board.*/
    private int indMax;
    
    /** Value which indicates current percentage of cases covered by the recursion.*/
    private double percentageCovered;
    
    /** 
     * Value needed to estimate time prediction till slowSolution finish.
     * Stores value of percentageCovered when last request was made by getTimePrediction.
     */
    private double lastRequestPercentage;
    
    /** 
     * Value needed to estimate time prediction till slowSolution finish.
     * Stores value of time when last request was made by getTimePrediction.
     */
    private long lastRequestTime;
    
    /** Indicates if thread should be running.*/
    private Boolean running;
    
    /** Indicates if thread should be stopped. but with possibility to be re-runned.*/
    private Boolean stoped;
    
    /** Stores value of previous prediction in milliseconds. */
    private double previousPrediction;    
    
    /** Indicates if thread needs to be completely finished. */
    private boolean finish;
    
    /** 
     * Deque which stores pairs(time prediction, 
     * and system time where prediction was made) of data.
     */
    private ArrayDeque<Pair<Double, Long>> deq;   
    
    /** Class which represents objects capable of storing pairs of data.*/
    public class Pair <F, S>{
        public F first;
        public S second;
        
        /** Default constructor.*/
        public Pair(F first, S second){
            this.first = first;
            this.second = second;
            
        }
    } 
    
    /** Default constructor. Assigns copy of given ClassicGrid to grid.*/
    public ClassicGridSolution(ClassicGrid originGrid){
    
        grid = originGrid.clone();
        
        turns = new Stack();
        
        emptyCellsNum = new ArrayList();  
        // fills emptyCellsNum with numbers of empty cells on the board.
        ArrayList<Integer> values = grid.getValues();
        for (int i=0; i<grid.getNumCells(); i++){
            if (values.get(i) ==0 ) emptyCellsNum.add(i);
        }
        
        solutionsFound = new ArrayList();
        
        indMax = (int) Math.pow(grid.getLevel(), 4);
        indMax--;
        
        percentageCovered = 0;
        lastRequestPercentage = 0;
        lastRequestTime = 0;
        
        previousPrediction = 0;       
        deq = new ArrayDeque();        
        
        running = true;
        stoped = false;
        finish = false;
    }
    
    /** 
     * !!!! Currently not in use !!!
     * 
     * Recursive method for finding solutions of grid. All found solutions 
     * got stored at solutionsFound ArrayList.
     * @param slice Indicates approximate percentage of cases covered with this recursion call, where 100 is all cases.     * 
     */  
    public void slowSolution(double slice){
        try {
            if (!running){ 
                synchronized (this){   
                    deq.clear();
                    this.wait(); // Pauses the thread if solution process should be paused.
                }
            }
            // In case of thread should be stoped
            if (stoped) {
                grid.userEraseValue(turns.pop()); // Erase last value from cell in the stack from the grid
                return;
            }

            // Basecase. Store solution. 
            if (grid.getUnsolvedCells() == 0 && !turns.empty()){
               solutionsFound.add(grid.getCopyGridMap());
               percentageCovered = percentageCovered + slice;
               /**
               System.out.println("Solution found ...");
               grid.printGrid(); 
               */ 
            } else { // Trying to add some value in first encountered empty cell.

                int copyLastTurn;
                if (!turns.empty()){
                    copyLastTurn = turns.peek(); // gets last turn made on a grid 
                } else copyLastTurn = -1; 

                boolean emptyFound = false;

                while (copyLastTurn < indMax){

                    copyLastTurn++;

                    if (grid.getCopyCell(copyLastTurn).getValue() == 0){ // if found empty cell     
                        emptyFound = true;

                        ArrayList<Integer> list = grid.getCopyCell(copyLastTurn).getPossibleValues();

                        if (list.isEmpty()) { 
                            copyLastTurn = indMax; // Current grid have no solutions, fall back.
                            percentageCovered = percentageCovered + slice;
                        } else {

                            Iterator<Integer> it = list.iterator();

                            while (it.hasNext()){
                                int value = it.next(); // Pick value from list
                                grid.userInsertValue(copyLastTurn, value); // Input new value
                                turns.push(copyLastTurn); // store this turn
                                this.slowSolution(slice/list.size()); // Going deeper into recursion.
                            }

                            copyLastTurn = indMax; // Prevents algorithm from skiping current empty cell and going to next one.
                        }

                    }
                }

                if (!emptyFound) percentageCovered = percentageCovered + slice;
            }

            // Before going back to caller need to clear last turn. 
            if (!turns.empty()) {
                grid.userEraseValue(turns.pop()); 
            }       
            
        } catch (InterruptedException ex) {               
                stoped = true;
                return;
        }
    }
    
    /** 
     * Another Recursive method for finding solutions of grid, with looking for 
     * cell with least possibleValues size inside recursion. 
     * All found solutions got stored at solutionsFound ArrayList.
     * @param slice Indicates approximate percentage of cases covered with this recursion call, where 100 is all cases. 
     */
    public void combinedSolution(double slice){
        
        try {
            if (!running){ 
                synchronized (this){    
                    deq.clear();
                    this.wait(); // Pauses the thread if solution process should be paused.
                }
            }
            // In case of thread should be stoped
            if (stoped) {
                grid.userEraseValue(turns.pop()); // Erase last value from cell in the stack from the grid
                return;
            }

            // Basecase. Store solution. 
            if (grid.getUnsolvedCells() == 0 && !turns.empty()){
               solutionsFound.add(grid.getCopyGridMap());
               percentageCovered = percentageCovered + slice;
               /**
               System.out.println("Solution found ...");
               grid.printGrid(); 
               */
            } else { // Trying to add some value in empty cell with least possible values.

                int min = grid.getLevel()+1; // minimal possibleValues size
                Integer cellNum = -1;
                boolean found = false;
                
                ArrayList<Integer> possibleValueSizes = grid.getPossibleValuesSizes();
                for (int i=0; i<emptyCellsNum.size(); i++){
                    
                    int size = possibleValueSizes.get(emptyCellsNum.get(i));
                    
                    if (size == 0) { // empty cell with no values to put in found. No solution in current grid. Fallback.
                        percentageCovered = percentageCovered + slice;
                        i = emptyCellsNum.size();
                        found = false;
                    } 
                    
                    if (size !=0 && size < min){
                        min = possibleValueSizes.get(emptyCellsNum.get(i)); 
                        cellNum = emptyCellsNum.get(i);
                        found = true;
                    }
                }
                
                if (found){
                    ClassicCell c = grid.getCopyCell(cellNum);
                    int size = c.getPossibleValues().size();
                    for (int i=0; i<size; i++){
                        emptyCellsNum.remove(cellNum); // this cell number is not empty anymore
                        turns.push(cellNum); // store this turn
                        grid.userInsertValue(cellNum, c.getPossibleValues().get(i)); // insert value to grid
                        combinedSolution(slice/size); // dive deeper into recursion
                    }
                }
            }

            // Before going back to caller need to clear last turn. 
            if (!turns.empty()) {
                emptyCellsNum.add(turns.peek());
                grid.userEraseValue(turns.pop()); 
            }       
            
        } catch (InterruptedException ex) {               
                stoped = true;
                return;
        }
    }
    
    /** 
     * Method which stops current solution search and resets this object or
     * restarts it from scratch.
     * @param mode true - to stop, false - to restart.
     */
    public void stop(boolean mode){
        stoped = mode;
    }
    
    /** 
     * Method which pauses or resumes current solution search. 
     * @param mode true - to pause, false - to resume.
     */
    public synchronized void plug(boolean mode){
        running = mode;
        if (mode) {
            notifyAll();
        }
    }
    
    /** Method which finishes solution thread completely. */
    public void finish(){
        finish = true;
        stoped = true;
        solutionsFound.clear();
        //System.out.println("Solution must stop now ...");
    };

    /** 
     * Method demanded by Runnable. Also, recursion caller.
     * Uses eternal loop to be able to start and restart search process.
     */
    @Override
    public void run() {
        //System.out.println("Solution started");
        while (!finish){ // Starts recursion. Once per second might restart search process.
            if (!stoped){
                
                solutionsFound.clear();
                deq.clear();
                turns.clear();
                percentageCovered = 0;
                lastRequestPercentage = 0;       
                previousPrediction = 0;
                
                lastRequestTime = System.currentTimeMillis();                
                //this.slowSolution(100);
                this.combinedSolution(100);
                //System.out.println("End of solution");
                if (!stoped) percentageCovered = 100;
                stoped = true;
            }
            try {
                Thread.sleep(1000);
            } catch (InterruptedException ex) {
                Logger.getLogger(ClassicGridSolution.class.getName()).log(Level.SEVERE, null, ex);
            }
        }
        //System.out.println("Solution stopped");
    }
    
    /** Returns number of solutions found.*/
    public int getNumSolFound(){
        return solutionsFound.size();
    }
    
    /** Returns copy of ArrayList with all solutions. */
    public ArrayList<TreeMap<Integer, ClassicCell>> getSolutions(){
        return (ArrayList<TreeMap<Integer, ClassicCell>>) solutionsFound.clone();
    }
    
    /** Returns percentageCovered value.*/
    public double getPercentageCovered(){
        return percentageCovered;
    }    
    
    /** 
     * Returns time estimate till slowSolution finish. 
     */
    public double getTimePrediction(){
        
        double currentPercentage = percentageCovered;
        long currentTime = System.currentTimeMillis();
        
        long timeDifference = currentTime - lastRequestTime;
        
        double instantPrediction = 0;
        try {
            /**
            System.out.print("\nCurrent percentage = " + currentPercentage +
                               "\nLast request percentage = " + lastRequestPercentage +
                               "\nPercentage difference = " + (currentPercentage - lastRequestPercentage) +
                               "\nTime difference = " + timeDifference);
             */
            if ((currentPercentage - lastRequestPercentage) !=0 )
                instantPrediction = (((100 - currentPercentage)/
                    (currentPercentage - lastRequestPercentage))*timeDifference);
        } catch (Exception e){
            // division by zero exception
        }
        
        double normalizedPrediction = 0;
        double predictionDifference = 0; // difference between instant and normalized prediction
        
        if (instantPrediction != 0){
            deq.addLast(new Pair(instantPrediction, currentTime));
            double deqSum = 0; // sum of all predictions in deque
            int size = deq.size();
            Iterator<Pair<Double,Long>> it = deq.iterator();
            while (it.hasNext()){
                Pair<Double, Long> p = it.next();
                // decreases this prediction by difference
                // of time this prediction was made and current system time. 
                p.first = p.first - (currentTime - p.second);  
                
                p.second = currentTime; // sets time this prediction was made to current system time
                deqSum = deqSum + (p.first)/size;
            }
            normalizedPrediction = deqSum;
            predictionDifference = Math.abs(previousPrediction - normalizedPrediction);
            if (predictionDifference < 60000) deq.removeFirst(); // prediction not accurate -> increase deque size
            // prediction too accurate -> decrease deque size
            if (predictionDifference < 10000 && !deq.isEmpty()) deq.removeFirst(); 
            
        } 
        
        lastRequestPercentage = currentPercentage;
        lastRequestTime = currentTime; 
        previousPrediction = normalizedPrediction;
        /**
        System.out.println("\nInstant prediction = " + instantPrediction +
                           "\nNormalized prediction = " + normalizedPrediction +
                           "\nPrediction difference " + predictionDifference +
                           "\nDeque size = " + deq.size() +
                           "\nTime to make prediction = " + (System.currentTimeMillis() - lastRequestTime) + "ms.");
        */
        return normalizedPrediction;
    }    
}
